//题目:
// 给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，
// 子集中每一元素对 (answer[i], answer[j]) 都应当满足：
// answer[i] % answer[j] == 0 ，或 answer[j] % answer[i] == 0
// 如果存在多个有效解子集，返回其中任何一个均可。

// 示例 1：
// 输入：nums = [1,2,3]
// 输出：[1,2]
// 解释：[1,3] 也会被视为正确答案。

// 示例 2：
// 输入：nums = [1,2,4,8]
// 输出：[1,2,4,8]
 
// 提示：
// 1 <= nums.length <= 1000
// 1 <= nums[i] <= 2 * 109
// nums 中的所有整数 互不相同
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) 
    {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        //1.创建dp表————dp[i]表示：以nums[i]为结尾的最大整除子集
        vector<vector<int>> dp(n);
        //2.初始化
        dp[0].push_back(nums[0]);
        //3.填表————动态转移方程:dp[i]=max(dp[i-1],带上nums[i]的子集);
        vector<int> ret=dp[0];
        for(int i=1;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
                if(nums[i]%nums[j]==0 && dp[i].size()<dp[j].size())
                    dp[i]=dp[j];
        
            dp[i].push_back(nums[i]);
            if(ret.size()<dp[i].size()) ret=dp[i];
        }
        //4.确定返回值
        return ret;
    }
};